package week07

// 438. 找到字符串中所有字母异位词
// https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

func findAnagrams(s string, p string) []int {
	var pcount = make(map[byte]int)
	var ccount = make(map[byte]int)
	for i := range p {
		pcount[p[i]]++
	}
	var ans []int
	// valid: “字符出现次数 == 在p中出现次数” 的字符数量
	var left, right, valid = 0, 0, 0
	for right < len(s) {
		ccount[s[right]]++
		if pcount[s[right]] > 0 && ccount[s[right]] == pcount[s[right]] {
			valid++
		}
		right++
		for valid == len(pcount) {	// 字符出现次数相等
			if right-left == len(p) {	// 长度相等
				ans = append(ans, left)
			}
			ccount[s[left]]--
			// 一直删到窗口中的字符无法组成 p 为止
			if v, ok := pcount[s[left]]; ok && v > ccount[s[left]] {
				valid--
			}
			left++
		}
	}
	return ans
}